1. Field
Embodiments of the present invention relate to systems and methods for encoding and decoding data in a communications channel.
2. Related Art
Run Length Encoding (RLE) is a popular lossless compression technique that represents data elements by “runs”—number of elements that have the same value in a certain scan order. For example, the following sequence “0,0,0,1,1,1,0,0,0,1,1” can be represented by “(0,3), (1,3), (0,3), (1,2)” where first number in each pair determines the value of the elements of the run and the second number determines the number of repetitions of that value. In the above example, the sequence starts with three 0s (0,3) followed by three is (1,3), followed by three more 0s (0,3), and finally two 1s (1,2). In the binary case, values of the elements can be omitted and the representation becomes “(3,3,3,2)” where first number of the RLE sequence refers to the number of repetitions of the element “0”.
Run length encoding is often used with hardware that operates in a raster-scan order such as display devices and scanners. The efficiency of RLE depends on characteristics of the data. For example, RLE provides higher compression when the number of different values is small and when the same values are often repeated in groups of adjacent elements. RLE can be applied to multidimensional data by applying a linear scan order on the data or by encoding number of repetitions directly in multiple dimensions. Typically, a RLE encoder operates on data that is provided in sequential order and stored in a line buffer or other types of memory. If data is produced in a non-sequential order, then the non-sequential data is generally buffered to complete the data so that it can be provided to the RLE encoder in sequential order.